#pragma once
#include <assert.h>
#include <iostream>
namespace bit
{
	template<class T>
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _last;
		T _data;
		ListNode(const T& x = T())
			:_next(nullptr)
			, _last(nullptr)
			, _data(x)
		{ }
	};
	template<class T>
	struct _list_iterator
	{
		typedef ListNode<T> Node;
		typedef _list_iterator<T> iterator;
		Node* node;
		_list_iterator(Node* p)
			:node(p)
		{   }
		T& operator*()
		{
			return node->_data;
		}
		iterator& operator++() //++it
		{
			node = node->_next;
			return *this;
		}
		iterator operator++(int) //it++
		{
			iterator tem(node);
			node = node->_next;
			return tem;
		}
		iterator& operator--()
		{
			node = node->_last;
			return *this;
		}
		iterator operator--(int)
		{
			iterator tem(node);
			node = node->_last;
			return tem;
		}
		bool operator==(const iterator& t)
		{
			return node == t.node;
		}
		bool operator!=(const iterator& t)
		{
			return node != t.node;
		}
	};
	template<class T>
	class list
	{
	public:
		typedef ListNode<T> Node;
		typedef _list_iterator<T> iterator;
		list()
		{
			_node = new Node;
			_node->_last = _node;
			_node->_next = _node;
		}
		list(list<T>& L)
		{
			*(this) = L;
		}
		list<T>& operator=(list<T>& L)
		{
			Node* node = (L._node)->_next;
			while (node != L._node)
			{
				push_back(node->_data);
				node = node->_next;
			}
			return *this;
		}
		~list()
		{
			Node* t = _node->_next;
			while (t != _node)
			{
				Node* next = t->_next;
				delete t;
				t = next;
			}
			delete t;
			t = nullptr;
		}
		iterator begin()
		{
			return _node->_next;
		}
		iterator end()
		{
			return _node;
		}
		void push_back(const T& x = T())
		{
			Node* node = new Node;
			node->_data = x;
			node->_next = _node;
			node->_last = _node->_last;
			_node->_last->_next = node;
			_node->_last = node;
		}
		void pop_back()
		{
			assert(_node->_next != _node);
			Node* node = _node->_last->_last;
			delete _node->_last;
			_node->_last = node;
			node->_next = _node;
		}
		void push_front(const T& x = T())
		{
			Node* node = new Node;
			node->_data = x;
			node->_next = _node->_next;
			node->_last = _node;
			_node->_next->_last = node;
			_node->_next = node;
		}
		void pop_front()
		{
			assert(_node->_next != _node);
			Node* node = _node->_next->_next;
			delete _node->_next;
			_node->_next = node;
			node->_last = _node;
		}
		void clear()
		{
			Node* t = _node->_next;
			while (t != _node)
			{
				Node* next = t->_next;
				delete t;
				t = next;
			}
			t = nullptr;
		}
		void swap(list<T>& L)
		{
			std::swap(_node, L._node);
		}
		iterator insert(iterator pos, const T& x = T())
		{
			Node* node = new Node;
			node->_data = x;
			node->_next = pos.node;
			node->_last = (pos.node)->_last;
			node->_next->_last = node;
			node->_last->_next = node;
			return node;
		}
		iterator erase(iterator pos)
		{
			assert(pos.node != _node);
			Node* next = (pos.node)->_next;
			Node* last = (pos.node)->_last;
			delete pos.node;
			next->_last = last;
			last->_next = next;
			return next;
		}
	private:
		Node* _node;
	};
	void test1()
	{
		list<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.pop_back();
		v.pop_front();
		v.push_front(8);
		v.push_front(9);
		for (auto e : v)
		{
			std::cout << e << "  ";
		}
		std::cout << std::endl;
	}
	void test2()
	{
		list<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		list<int>::iterator it = ++v.begin();
		v.insert(it, 9);
		v.erase(v.begin());
		for (auto e : v)
		{
			std::cout << e << "  ";
		}
		std::cout << std::endl;
	}
	void test3()
	{
		list<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		list<int> v2;
		v2 = v1;
		for (auto e : v2)
		{
			std::cout << e << "  ";
		}
		std::cout << std::endl;
	}
}